package xio.leetcode.java;

import xio.leetcode.java.base.ListNode;

/**
 * leetcode 148. sort List
 *
 * 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
 *
 * 示例 1:
 *
 * 输入: 4->2->1->3
 * 输出: 1->2->3->4
 *
 * *说明：当前代码的是 归并排序的top-down版本，时间复杂度是 O(nlogn) ，但空间复杂度是O(logn)，所以虽然能通过 oj，但不符合题目要求
 */
public class LC148_SortList {

    /**
     * 链表的归并排序
     * @param head 链表的头节点
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        // 快慢指针的方式找到中间点
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode mid = slow.next;
        // 按中间点进行分割
        slow.next = null;
        // 递归进行归并
        return merge(sortList(head), sortList(mid));
    }

    /**
     * 合并有序两个链表
     * @param l1 链表 l1
     * @param l2 链表 l2
     * @return 合并后的有序链表
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                ListNode tmp = l1;
                l1 = l2;
                l2 = tmp;
            }
            tail.next = l1;
            l1 = l1.next;
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}
